public class a7 {
    public static int trap(int[] height) {
        int[] pre_max = new int[height.length];
        int[] suf_max = new int[height.length];
        pre_max[0] = height[0];
        suf_max[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            pre_max[i] = Math.max(height[i], pre_max[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            suf_max[i] = Math.max(suf_max[i + 1], height[i]);
        }
        int count = 0;
        for (int i = 0; i < height.length; i++) {
            count += Math.min(pre_max[i], suf_max[i]) - height[i];
        }

        return count;
    }

    public static int trap2(int[] height) {
        int count = 0;
        int right = height.length - 1, left = 0;
        int pre_max = 0;
        int suf_max = 0;
        while (left <= right) {
            pre_max = Math.max(pre_max, height[left]);
            suf_max = Math.max(suf_max, height[right]);
            if (pre_max < suf_max) {
                count += pre_max - height[left];
                left++;
            } else {
                count += suf_max - height[right];
                right--;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap2(nums));
    }
}
